package prac10;

import java.util.List;
import java.util.LinkedList;

/*  generic Hash Table data type implemented using separate chaining 
 *  techniques
 * 
 * @author Menghong Li,
 * 
 * @since    13-10-2011
 * @input   none
 * @output  none
 * @errorHandling   none
 * @knownBugs   none
 */
public class SeparateChaining<K extends Hashable, D> {

    private Element[] hashTable;
    private int collisions = 0;
    private int probes = 0;
    
    /**
     * internal class for each chain
     */
    private class Element {

        private int number;
        private List<Entry> theChain;
        
        /**
         * constructs a new chain
         * @complexity O(L)
         *              where L is the complexity of {@link LinkedList#LinkedList() }
         */
        public Element() {
            theChain = new LinkedList<Entry>();
            number = 0;
        }
        
        /**
         * adds a new entry to the chain
         * @post the entry will be a the front of the list
         * @param entry the entry to be added
         * @complexity O(A)
         *              where A is the complexity of {@link LinkedList#add(java.lang.Object) }
         */
        public void add(Entry entry) {
            theChain.add(entry);
            number++;
        }

        /**
         * returns the number of items in the current chain
         * 
         * @return the number of items
         * @complexity O(1)
         */
        public int getNumber() {
            return number;
        }
    }
    
     /**
     * invariant: if an Entry is stored in position N, then
     *      N is either the hash value of the Entry's key K, or the first empty 
     *      position from the hash value when Entry was inserted. 
     * invariant (corollary of the above, really): there are
     *      no empty spaces between items with the same hash value.
     */
    private class Entry {

        K key;
        D data;

        private Entry(K newKey, D newData) {
            key = newKey;
            data = newData;
        }

        private K getKey() {
            return key;
        }

        private D getData() {
            return data;
        }

        public String toString() {
            return key + "::" + data;
        }
    }
    
    /**
     * instantiates a new SeprateChaining hashTable 
     * 
     * @param size the size of the hashTable
     * @complexity O(C)
     *              where C is the complexity of {@link Chain#Chain() }
     */
    public SeparateChaining(int size) {
        hashTable = new SeparateChaining.Element[size];
        collisions = 0;
        probes = 0;
    }

    /**
     * returns the total number of collisions for the life of this
     * hash table
     * 
     * @complexity O(1) for best and worst case
     * @return number of collisions 
     */
    public int getCollisions() {
        return collisions;
    }

    /**
     * returns the total number of probes for the life of this
     * hash table
     * 
     * @complexity O(1) for best and worst case
     * @return number of probes 
     */
    public int getProbes() {
        return probes;
    }

    /**
     * Inserts a new element into the hash table. It returns true if the item 
     * is inserted in the first empty slot from the associated hash value
     *
     * @pre  the element does not already appear in the table
     * @post if it returns false, hashTable is full and left unchanged. If
     *       it returns true, hashTable has a new element, and all cells from
     *       "position" to where Entry(key,data) is finally added to, are full
     * @complexity O(H + E + A) for the best case and O(H + C + E + A) for worst case
     *              where H is the complexity of {@link Word#hash() }
     *              where E is the complexity of {@link SeparateChaining#Entry#Entry() }
     *              where A is the complexity of {@link SeparateChaining#Chain#add() }
     *              where C is the complexity of {@link SeparateChaining#Chain#Chain() }
     * @return  true always
     */
    public boolean insert(K key, D data) {
        int position = key.hash();

        if (hashTable[position] != null) {
            collisions++;
        } else {
            hashTable[position] = new Element();
        }
        Entry tmp = new Entry(key, data);
        hashTable[position].add(tmp);
        
        return true;
    }

    /**
     * Searches for the data associated to a particular key (if any).
     * It returns D if it can find the item, null if it cannot
     *
     * @pre none
     * @post If it returns null, there is no cell in hashTable with 
     *       the chosen key, if it returns D, then a cell with that key exists, 
     *       and has D as data. Also, hashTable is unchanged.
     * @complexity Best case: O(A) when the hash points to null in the hashTable
     * @complexity Worst case: O(A + CHAINSIZE * E + G)
     *                  where A is the complexity of {@link Word#hash() }
     *                  where CHAINSIZE is the number of entries in the Chain
     *                  where E is the complexity of {@link Object#equals(java.lang.Object) }
     *                  where G is the complexity of getData() which is O(!)
     */
    public D search(K key) {
        int position = key.hash();
        if (hashTable[position] == null) {
            return null;
        } else {
        	collisions++;
            for (Entry mEntry : hashTable[position].theChain) {
                if (mEntry.getKey().equals(key)) {
                	probes++;
                    return mEntry.getData();
                } else {
                    probes++;
                }
            }
        }
        return null;
    }
    
    /**
     * Used to print all elements in the hashTable, each in a line
     *
     * @pre none new
     * @post the hashTable is unchanged
     * @complexity best and worst case of O(TABLESIZE * CHAINSIZE * printLine()) 
     */
    public void printItems() {
        for (Element mChain : hashTable) {
            if (mChain != null) {
                for (Entry mEntry : mChain.theChain) {
                    System.out.println(mEntry);
                }
            }
        }
    }
}
